package 代码随想录_动态规划.子序列问题.不连续;

/**
 * @author zx
 * @create 2022-06-05 16:41
 * 题目分析：
 * 绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且直线不能相交！
 * 直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，
 * 链接相同数字的直线就不会相交。
 * 本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！
 * 所以就是1143题的解法
 * 组成部分一：确定状态
 *               最后一步：
 *               子问题：
 *               确定dp数组(dp table)以及下标的含义
 * 组成部分一：确定状态
 * 最后一步：
 * 子问题：
 * 组成部分二：转移方程
 * 组成部分三：初始条件和边界情况
 * 组成部分四：计算顺序
 */
public class 不相交的线_1035 {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        //dp[i][j][0,i-1]的字符串nums1与长度为[0,j-1]的nums2的最长公共子序列为dp[i][j]
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int res = 0;
        //dp[i][j]的定义决定着,遍历dp[i][j]的时候i 和 j都要从1开始。
        for(int i = 1;i <= nums1.length;i++){
            for(int j = 1;j <= nums2.length;j++){
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i][j - 1],dp[i - 1][j]);
                }
                res = Math.max(res,dp[i][j]);
            }
        }
        return res;
    }
}
